package 递归回溯;

import java.util.ArrayList;
import java.util.List;

public class No93复原IP地址 {

    /**
     * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
     * 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
     * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，
     * 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
     *
     * 示例 1：
     * 输入：s = "25525511135"
     * 输出：["255.255.11.135","255.255.111.35"]
     * 示例 2：
     * 输入：s = "0000"
     * 输出：["0.0.0.0"]
     * 示例 3：
     * 输入：s = "1111"
     * 输出：["1.1.1.1"]
     * 示例 4：
     * 输入：s = "010010"
     * 输出：["0.10.0.10","0.100.1.0"]
     */

    //感觉这个非常难,就用4个for循环解决得了
    public List<String> restoreIpAddresses(String s) {

        List<String> list=new ArrayList<>();
        if(s.length()<4||s.length()>12)
            return list;
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=0;i<4;i++){
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    for (int l = 0; l < 4; l++) {
                        if(i+j+k+l==s.length()){
                            //符合题目长度进入
                            String a=s.substring(0,i);
                            Integer aI=Integer.parseInt(a);
                            String b=s.substring(i,i+j);
                            Integer bI=Integer.parseInt(b);
                            String c=s.substring(i+j,i+j+k);
                            Integer cI=Integer.parseInt(c);
                            String d=s.substring(i+j+l);
                            Integer dI=Integer.parseInt(d);
                            if(aI>=0&&aI<=255&&bI>=0&&bI<=255&&cI>=0&&cI<=255&&dI>=0&&dI<=255){
                                stringBuilder.append(a).append(".").append(b)
                                        .append(".").append(c).append(".").append(d);
                                //杜绝001这种情况发生
                                if(stringBuilder.length()==s.length()+3)
                                    list.add(stringBuilder.toString());
                                stringBuilder.delete(0,stringBuilder.length());
                            }
                        }
                    }
                }
            }
        }
        return list;
    }

}
